package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC592 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public String fractionAddition(String expression) {
            LinkedList<Character> opStack = new LinkedList<>();
            LinkedList<Integer> denominatorStack = new LinkedList<>();
            LinkedList<Integer> numeratorStack = new LinkedList<>();

            int curNum = 0;
            for (int i = 0; i < expression.length(); i++) {
                char c = expression.charAt(i);
                if ('+' == c || '-' == c) {
                    opStack.add(c);
                    if (!numeratorStack.isEmpty()) denominatorStack.add(curNum);
                    curNum = 0;
                } else if ('/' == c) {
                    numeratorStack.add(curNum);
                    curNum = 0;
                } else {
                    if (i == 0) opStack.add('+');
                    curNum = curNum * 10 + c - '0';
                }
            }
            denominatorStack.add(curNum);

            if (denominatorStack.size() <= 1) {
                int commonSum = ('-' == opStack.get(0) ? -1 : 1) * numeratorStack.get(0), commonBase = denominatorStack.get(0);
                int maxCommonDivisor = maxCommonDivisor(Math.abs(commonSum), Math.abs(commonBase));
                commonSum /= maxCommonDivisor;
                commonBase /= maxCommonDivisor;
                return commonSum + "/" + commonBase;
            }
            int commonBase = denominatorStack.get(0), cur = 0;
            for (int i = 1; i < denominatorStack.size(); i++) {
                cur = denominatorStack.get(i);
                commonBase = minCommonMultiple(commonBase, cur);
            }

            int commonSum = 0;
            Character op;
            for (int i = 0; i < numeratorStack.size(); i++) {
                cur = numeratorStack.get(i);
                op = opStack.get(i);
                int curBase = denominatorStack.get(i);
                commonSum += ('-' == op ? -1 : 1) * cur * (commonBase / curBase);
            }

            if (0 == commonSum) return "0/1";
            int maxCommonDivisor = maxCommonDivisor(Math.abs(commonSum), Math.abs(commonBase));
            commonSum /= maxCommonDivisor;
            commonBase /= maxCommonDivisor;
            return commonSum + "/" + commonBase;
        }

        // 递归法求最大公约数
        public int maxCommonDivisor(int m, int n) {
            if (m < n) {// 保证m>n,若m<n,则进行数据交换
                int temp = m;
                m = n;
                n = temp;
            }
            if (m % n == 0) {// 若余数为0,返回最大公约数
                return n;
            } else { // 否则,进行递归,把n赋给m,把余数赋给n
                return maxCommonDivisor(n, m % n);
            }
        }

        // 求最小公倍数
        public int minCommonMultiple(int m, int n) {
            return m * n / maxCommonDivisor(m, n);
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.fractionAddition("-7/3"));
    }

    public static void main(String[] args) throws Exception {
        LC592 an = new LC592();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
